#include<iostream>
#include<vector>
#include<stack>
using namespace std;


class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> left;
        vector<int> right;
        stack<int> tmpSt;
        int len = heights.size();
        left.resize(len); right.resize(len);
        for (int i = 0; i < len; i++) {
            while (!tmpSt.empty() && heights[tmpSt.top()] >= heights[i]) {
                tmpSt.pop();
            }
            left[i] = tmpSt.empty() ? -1 : tmpSt.top();
            tmpSt.push(i);
        }
        // for(auto& e : left){
        //     cout << e << endl;
        // }
        tmpSt = stack<int>();
        for (int i = len - 1; i >= 0; i--) {
            while (!tmpSt.empty() && heights[tmpSt.top()] >= heights[i]) {
                tmpSt.pop();
            }
            right[i] = tmpSt.empty() ? len : tmpSt.top();
            tmpSt.push(i);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
            // printf("i:%d,left[i]:%d,right[i]:%d,height[i]:%d, ans:%d\n",i, left[i],right[i],heights[i], (right[i] - left[i]) * heights[i]);
        }
        return ans;
    }
};